#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;

typedef struct LNode
{
	int digit;
	struct LNode *next;
}tLNode;

void createList(tLNode *&head, int array[], int n);
void addNode(tLNode *p , int val);
tLNode* sumList(tLNode *&l1,tLNode *&l2);
void Handle(tLNode *&head);
void display(tLNode *p);

void 
createList(tLNode *&head,int array[],int n)
{
	head = new tLNode();
	head->next = NULL;
	for(int i=0;i<n;i++)
	{
		addNode(head,array[i]);
	}
}

void 
addNode(tLNode *p,int val)
{
	tLNode *s = new tLNode();
	while(p->next!=NULL)
	{
		p=p->next;
	}
	s->digit = val;
	s->next = NULL;
	p->next = s;
}

tLNode* 
sumList(tLNode *&l1,tLNode *&l2)
{
	tLNode *head = new tLNode();
	head->next = NULL;

	while(l1->next!=NULL && l2->next!=NULL)
	{
		l1=l1->next; l2=l2->next;
		addNode(head,l1->digit+l2->digit);
	}	

	if(l1->next == NULL && l2->next == NULL)
	{
		Handle(head);
		return head;
	}
	else if(l1->next == NULL)
	{
		while(l2->next!=NULL)
		{
			l2=l2->next;		
			addNode(head,l2->digit);
		}
		Handle(head);
		return head;
	}
	else if(l2->next == NULL)
	{
		while(l1->next!=NULL)
		{
			l1=l1->next;
			addNode(head,l1->digit);
		}
		Handle(head);
		return head;
	}
}

void Handle(tLNode *&head)
{
	tLNode *p = head;
	while(p->next->next!=NULL)
	{
		p=p->next;
		if(p->digit>=10) 
		{
			p->next->digit += (p->digit)/10;
			p->digit=(p->digit)%10;
		}
	}

	p=p->next;
	if(p->digit < 10) return;
	else 
	{
		addNode(head,(p->digit)/10);
		p->digit=(p->digit)%10;
		return; 
	}
}

void display(tLNode *p)
{
	while(p->next!=NULL)
	{
		p=p->next;
		cout<<p->digit<<" ";
	}
	cout<<endl;
}

int 
main()
{
	int a1[]={3,1,5};
	int a2[]={5,9,2};
	int b1[]={2,8,8};
	int b2[]={9,5,5,9};
	
	tLNode *La1=NULL,*La2=NULL,*Lb1=NULL,*Lb2=NULL;
	createList(La1,a1,sizeof(a1)/sizeof(a1[0]));
	createList(La2,a2,sizeof(a2)/sizeof(a2[0]));
	createList(Lb1,b1,sizeof(b1)/sizeof(b1[0]));
	createList(Lb2,b2,sizeof(b2)/sizeof(b2[0]));

	cout<<"display la1:"<<endl;
	display(La1);
	cout<<"display la2:"<<endl;
	display(La2);
	cout<<"display lb1:"<<endl;
	display(Lb1);
	cout<<"display lb2:"<<endl;
	display(Lb2);

	cout<<"La1 + La2 = "<<endl;
	tLNode *p = sumList(La1,La2);
	display(p);

	cout<<"Lb1 + Lb2 = "<<endl;
	p = sumList(Lb1,Lb2);
	display(p);

	return 0;
}
